Linked list components

Time: O(M+N); Space: O(M); medium

We are given head, the head node of a linked list containing unique integer values.

We are also given the list G, a subset of the values in the linked list.

Return the number of connected components in G, where two values are connected if they appear consecutively in the linked list.

Example 1:

Input: head = {ListNode} 0->1->2->3->None, G = [0, 1, 3]

Output: 2

Explanation:

  • 0 and 1 are connected, so [0, 1] and [3] are the two connected components.

Example 2:

Input: head = {ListNode} 0->1->2->3->4->None, G = [0, 3, 1, 4]

Output: 2

Explanation:

  • 0 and 1 are connected, 3 and 4 are connected, so [0, 1] and [3, 4] are the two connected components.

Constraints:

  • If N is the length of the linked list given by head, 1 <= N <= 10000.

  • The value of each node in the linked list will be in the range [0, N - 1].

  • 1 <= len(G) <= 10000.

  • G is a subset of all values in the linked list.

[5]:

class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None

1. Grouping

Intuition

Instead of thinking about connected components in G, think about them in the linked list. Connected components in G must occur consecutively in the linked list.

Algorithm

Scanning through the list, if node.val is in G and node.next.val isn’t (including if node.next is null), then this must be the end of a connected component.

For example, if the list is 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7, and G = [0, 2, 3, 5, 7], then when scanning through the list, we fulfill the above condition at 0, 3, 5, 7, for a total answer of 4.

[6]:

class Solution1(object):
    """
    Time: O(N+len(G)), where N is the length of the linked list with root node head.
    Space: O(len(G)), to store G set.
    """
    def numComponents(self, head, G):
        Gset = set(G)
        cur = head
        ans = 0
        while cur:
            if (cur.val in Gset and
                    getattr(cur.next, 'val', None) not in Gset):
                ans += 1
            cur = cur.next

        return ans

[7]:

s = Solution1()

head = ListNode(0)
head.next = ListNode(1)
head.next.next = ListNode(2)
head.next.next.next = ListNode(3)
G = [0, 1, 3]
assert s.numComponents(head, G) == 2

head = ListNode(0)
head.next = ListNode(1)
head.next.next = ListNode(2)
head.next.next.next = ListNode(3)
head.next.next.next.next = ListNode(4)
G = [0, 3, 1, 4]
assert s.numComponents(head, G) == 2

[8]:

class Solution1a(object):
    """
    Time: O(N+len(G)), where N is the length of the linked list with root node head.
    Space: O(len(G)), to store G set.
    """
    def numComponents(self, head, G):
        """
        :type head: ListNode
        :type G: List[int]
        :rtype: int
        """
        lookup = set(G)
        dummy = ListNode(-1)
        dummy.next = head
        curr = dummy
        result = 0

        while curr and curr.next:
            if curr.val not in lookup and curr.next.val in lookup:
                result += 1
            curr = curr.next

        return result

[9]:

s = Solution1a()

head = ListNode(0)
head.next = ListNode(1)
head.next.next = ListNode(2)
head.next.next.next = ListNode(3)
G = [0, 1, 3]
assert s.numComponents(head, G) == 2

head = ListNode(0)
head.next = ListNode(1)
head.next.next = ListNode(2)
head.next.next.next = ListNode(3)
head.next.next.next.next = ListNode(4)
G = [0, 3, 1, 4]
assert s.numComponents(head, G) == 2